Histone acetylation is a prominent epigenetic modification linked to the memory loss symptoms associated with neurodegenerative disease. The use of existing histone deacetylase inhibitor (HDACi) drugs for treatment is precluded by their weak blood-brain barrier (BBB) permeability and undesirable toxicity. Here, we address these shortcomings by developing a new class of disulfide-based compounds, inspired by the scaffold of the FDA-approved HDACi romidepsin (FK288). Our findings indicate that our novel compound MJM-1 increases the overall level of histone 3 (H3) acetylation in a prostate cancer cell line. In mice, MJM-1 injected intraperitoneally (i.p.) crossed the BBB and could be detected in the hippocampus, a brain region that mediates memory. Consistent with this finding, we found that the post-training i.p. administration of MJM-1 enhanced hippocampus-dependent spatial memory consolidation in male mice. Therefore, MJM-1 represents a potential lead for further optimization as a therapeutic strategy for ameliorating cognitive deficits in aging and neurodegenerative diseases.